/* Copyright 2014 Jan Wolter */

#include "stack.h"
#include "solve.h"
#include "stock.h"
#include "bouquet.h"
#include "waste.h"
#include "found.h"
#include "game.h"
#include "dfs.h"
#include <signal.h>

/* For planned moves, MTYPE_DEAL means we are dealing new card(s) from the stock.
 * But that type of move is never put on the move history stack. Instead the series
 * of MTYPE_STD stack->to->stack movements that represents are pushed on.
 */

int passcnt,movecnt,backtracks;
int bestQuality,bestLength;
SavedMove *bestSoln= NULL;
Stack *init_stacks;
Stack **end_state= NULL;
int n_end_state,size_end_state= 0;
Move *hist;
int redealOnlyWhenStuck= 0;

/* Push the current state of the game onto the end_state stack. This is done just
 * before a pickup-and-redeal.
 */
void pushEndState()
{
   if (n_end_state >= size_end_state)
   {
       size_end_state= n_end_state + 4;
       end_state= (Stack **)realloc(end_state, size_end_state * sizeof (Stack *));
   }
   end_state[n_end_state++]= dupStacks(stacks, nstacks);
}

/* Pop the most recent end state off the end_state stack and make it our current
 * state. This is done to undo a pickup-and-redeal.
 */
void popEndState()
{
    if (n_end_state > 0)
    {
	copyStacks(stacks, end_state[--n_end_state], nstacks, 0);
	cleanDup(end_state[n_end_state]);
    }
}

/* Deallocate the given move and all it's alternatives */
void freeAlt(Move *m)
{
    while (m != NULL)
    {
	Move *next= m->alt;
	free(m);
	m= next;
    }
}

/* Deallocate the entire history */
void freeHist(Move *hist)
{
    Move *prev, *m;

    for (m= hist; m != NULL; m= prev)
    {
	prev= m->prev;
	freeAlt(m);
    }
}

/* Generate a string describing a move. If "planned" is true then this is
 * a contemplated move, not an actual move, which makes a different for
 * card deals.
 */
char *moveStr(Move *m, int undo, int planned)
{
    char cn[1024];
    static char out[1024];
    cn[0]= '\0';
    Stack *s= stacks + m->srcid;
    if (m->type == MTYPE_DEAL)
    {
	strcpy(out,undo ? "Undeal" : "Deal");
	return out;
    }
    if (m->type == MTYPE_REDEAL)
    {
	strcpy(out,undo ? "Undo Redeal" : "Redeal");
	return out;
    }
    Stack *d= stacks + m->dstid;

    if (undo)
    {
	if (d->n < m->len)
	{
	    printf("Undo Fails - Insufficient cards\n");
	    exit(1);
	}
	for (int i= d->n - m->len; i < d->n; i++)
	{
	    if (cn[0] != '\0') strcat(cn," ");
	    strcat(cn,cardname(d->c[i]));
	}
	sprintf(out,"[%s] %c%02d <- %c%02d", cn,
	    TYPECHAR[s->type], s->tid+1, TYPECHAR[d->type], d->tid+1);
    }
    else
    {
	if (s->n < m->srci + m->len)
	{
	    printf("Move Fails - Insufficient cards\n");
	    exit(1);
	}
	for (int i= m->srci; i < m->srci + m->len; i++)
	{
	    if (cn[0] != '\0') strcat(cn," ");
	    strcat(cn,cardname(s->c[i]));
	}
	sprintf(out,"[%s] %c%02d -> %c%02d (%d)", cn,
	    TYPECHAR[s->type], s->tid+1, TYPECHAR[d->type], d->tid+1, m->score);
    }
    return out;
}


/* Execute the move described by the given move object. Will update the
 * move->flip flag in the move object if we need to flip a card.
 */
void doMove(Move *m)
{
    Stack *s= stacks + m->srcid;

    /* A planned redeal from the stock is a deal, which may actually expand out
     * into multiple moves on the history stack.
     */
    if (m->type == MTYPE_DEAL)
    {
	dealStock(0, &hist, m->alt);
	free(m);
	return;
    }

    char *ms;
    if (verbose > 2) ms= moveStr(m,0,0);

    if (m->type == MTYPE_REDEAL)
    {
	/* A pickup/redeal means pushing the current state onto the end_state
	 * stack, and then calling the game specific pickup_redeal() function */
	pushEndState();
	pickup_redeal(stacks);
    }
    else
    {
	/* A simple card/stack move */
	Stack *d= stacks + m->dstid;

	/* Move the cards */
	insertStack(d, d->n, m->len, s->c+m->srci, m->reverse);
	removeStack(s, m->srci, m->len);

	/* Do we need to flip the next card in the source stack? */
	Card *top= topStack(s);
	if (top && !top->faceup)
	    m->flip= top->faceup= 1;
	else
	    m->flip= 0;

	/* If we moved from a bouquet record the old 'top' value and set the new */
	if (s->type == BOUQUET)
	{
	    m->btop= bouquet[s->tid].top;
	    bouquet[s->tid].top= m->srci - 1;
	}
    }

    movecnt++;

    if (s->postMove) s->postMove(s);

    if (verbose > 2)
	printf("%3d: %s\n",movecnt, ms);

    /* Put the move on the history */
    m->prev= hist;
    hist= m;
}


/* Undo the move described by the given move object.
 */
void undoMove(Move *m)
{
    char *ms;
    if (verbose > 2)
	ms= moveStr(m,1,0);

    if (m->type == MTYPE_REDEAL)
    {
	popEndState();
    }
    else
    {
	Stack *s= stacks + m->srcid;
	Stack *d= stacks + m->dstid;

	/* If undoing a move from the bouquet, reset the old 'top' value */
	if (s->type == BOUQUET)
	    bouquet[s->tid].top= m->btop;

	if (m->flip)
	{
	    Card *c= topStack(s);
	    if (c) c->faceup= 0;
	}

	insertStack(s, m->srci, m->len, d->c + d->n - m->len, m->reverse);
	d->n-= m->len;
    }

    movecnt--;

    if (verbose > 2)
	printf("%3d: %s\n",movecnt, ms);
}

void saveBest(int gather)
{
    /* If we aren't reporting solutions, then don't save them either */
    if (verbose == 0 && !gather) return;

    /* Is this better than what we've seen before? */
    int q= quality();
    if (q <= bestQuality) return;
    bestQuality= q;

    /* If this ends up being the best solution, and if we are gathering, then
     * we'd better gather this.
     */
    if (gather) gatherAll();

    if (verbose == 0) return;

    bestLength= movecnt;

    if (bestSoln != NULL) free(bestSoln);
    bestSoln= (SavedMove *)malloc(movecnt * sizeof(SavedMove));

    int i;
    Move *p;
    for (p= hist, i= movecnt-1; p != NULL; p= p->prev, i--)
    {
	bestSoln[i].type= p->type;
	bestSoln[i].srcid= p->srcid;
	bestSoln[i].srci= p->srci;
	bestSoln[i].len= p->len;
	bestSoln[i].dstid= p->dstid;
	bestSoln[i].reverse= p->reverse;
    }
}

void printBest(FILE *f, int final)
{
    if (bestSoln == NULL || bestLength == 0)
    {
	fprintf(f,"No Moves Possible\n");
	return;
    }

    /* Make a local copy of the initial state */
    Stack *stks= dupStacks(init_stacks, nstacks);
    char cn[1024];

    /* Replay the game */
    for (int i= 0; i < bestLength; i++)
    {
	if (bestSoln[i].type == MTYPE_REDEAL)
	{
	    pickup_redeal(stks);
	    fprintf(f,"%3d: REDEAL\n",i+1);
	    printState(f, stks);
	}
	else
	{
	    Stack *s= stks + bestSoln[i].srcid;
	    Stack *d= stks + bestSoln[i].dstid;

	    /* Find a description of the set of cards being moved */
	    if (s->type == WASTE && d->type == STOCK)
		strcpy(cn,"All Cards");
	    else
	    {
		cn[0]= '\0';
		for (int j= bestSoln[i].srci;
		     j < bestSoln[i].srci+ bestSoln[i].len; j++)
		{
		    Card *c= s->c[j];
		    if (cn[0] != '\0') strcat(cn," ");
		    strcat(cn,cardname(c));
		}
	    }

	    /* Move the cards */
	    insertStack(d, d->n, bestSoln[i].len, s->c+bestSoln[i].srci,
		bestSoln[i].reverse);
	    removeStack(s, bestSoln[i].srci, bestSoln[i].len);

	    /* Print the move */
	    fprintf(f,"%3d: [%s] %c%02d -> %c%02d\n", i+1,cn,
		TYPECHAR[s->type], s->tid+1, TYPECHAR[d->type], d->tid+1);
	}
    }

    if (final)
	printState(f, stks);

    cleanDup(stks);
}

void intr(int sig)
{
    char buf[1024];
    int verb;

    signal(SIGINT, intr);

    fflush(stdout);

    fprintf(stderr,"\nRun=%d Best Quality=%d Visited=%d Curr Depth=%d\n",
	    runcnt,bestQuality,nVisited(),movecnt);
    for (;;)
    {
	fprintf(stderr,"Continue [ynsbv]? ");
	if (!fgets(buf,1023,stdin)) {putc('\n',stderr); exit(1);}
	switch (buf[0])
	{
	case 'n': case 'N':
	    fprintf(stderr,"Goodbye\n");
	    exit(1);

	case 'y': case 'Y':
	case 'c': case 'C':
	    return;

	case 'b': case 'B':
	    printBest(stderr, 1);
	    break;

	case 'v': case 'V':
	    verb= -1;
	    sscanf(buf+1,"%d",&verb);
	    if (verb >= 0 && verb <= 5)
		verbose= verb;
	    break;

	case 's': case 'S':
	    printState(stderr, stacks);
	    break;
	}
    }
}

/* Insert a new move into its sorted position on the list of alternate moves */
void insertAltMove(Move **movehead, Move *newmove, int score)
{
    Move *p, *n;
    for (p= NULL, n= *movehead;
	 n != NULL && score > n->score;
	 p=n, n= p->alt)
	;
    if (p == NULL)
    {
	newmove->alt= *movehead;
	*movehead= newmove;
    }
    else
    {
	newmove->alt= n;
	p->alt= newmove;
    }
}

/* Found a move candidate.
 * Returns
 *    -1: move is no good, keep looking;
 *     1: move has been made, start next loop;
 *     0: move has been added to moves list, look for more
 */
int savemove(int type, int si, int index1, int len, int di, Move **moves)
{
    /* Found a possible move */
    int score;

    if (type == MTYPE_STD)
	score= rateMove(stacks+si, index1, len, stacks+di);
    else
	score= rateRedeal();
    if (score < 0) return -1;
    Move *thisMove= newMove(type, si, index1, len, di, score, 0);
    /* Safe moves are only safe if we have no redeals */
    if (score == 0 && (redealOnlyWhenStuck || rateRedeal() < 0))
    {
	/* A Safe Move - do it right away */
	doMove(thisMove);
	/* Discard any alternate moves we found */
	freeAlt(*moves);
	*moves= NULL;
	return 1;
    }

    /* An Unsafe move - add it to alternative list.
     * We keep the alternatives list in sorted order
     * with the lowest score moves first.
     */
    insertAltMove(moves, thisMove, score);
    return 0;
}

void cleanUp(int keepinit)
{
    if (!keepinit) cleanDup(init_stacks);
    freeHist(hist);
    for (int i= 0; i < n_end_state; i++)
	cleanDup(end_state[i]);
    if (size_end_state > 0) free(end_state);
    size_end_state= n_end_state= 0;
    end_state= NULL;
}

/* A simple dfs solver */

int solve(int gather, int keepinit)
{
    passcnt= 1;
    backtracks= movecnt= 0;
    n_end_state= 0;
    Move *moves= NULL;
    bestQuality= -1;
    if (bestSoln != NULL) free(bestSoln);
    bestSoln= NULL;
    hist= NULL;

    /* Save a copy of the initial state for use by printBest() */
    init_stacks= dupStacks(stacks, nstacks);

    signal(SIGINT, intr);

    while (!victory())
    {
	/* Save the current state. If we've been in this state before,
	 * then don't look for moves. Just backtrack.
	 */
	int v= visitedState(currstate());
	if (v < 0)
	{
	    if (verbose > 0)
		printf("Abandoned! pass=%d moves=%d backtracks=%d\n",
		    passcnt,movecnt,backtracks);
	    if (verbose > 1)
		printBest(stdout, 1);
	    cleanUp(keepinit);
	    return 2;
	}

	if (!v)
	{
	    /* Find all possible moves */
	    for (int i= 0; i < nsrc; i++)
	    {
		int index1, len;
		Stack *s= stacks+srclist[i];
		for (int rc= s->firstMove(s, &index1, &len); rc;
			rc= s->nextMove(s, &index1, &len))
		{
		    /* If we have a foundation superhandler configured,
		     * try that.
		     */
		    if (superfound != NULL)
		    {
			int dsti= superfound(s,index1,len);
			if (dsti >= 0)
			{
			    /* Found a possible move */
			    int rc= savemove(MTYPE_STD, srclist[i], index1,
				len, dsti, &moves);
			    /* Rejected move */
			    if (rc < 0) continue;
			    /* Safe move */
			    if (rc > 0) goto nextstep;
			}
		    }

		    /* Search list of possible destination stacks */
		    for (int j= 0; j < ndst; j++)
		    {
			Stack *d= stacks+dstlist[j];
			if (s == d) continue;
			if (d->mayInsert(d, s->c[index1], len, s))
			{
			    /* Found a possible move */
			    int rc= savemove(MTYPE_STD,srclist[i], index1, len,
				dstlist[j], &moves);
			    /* Rejected move */
			    if (rc < 0) continue;
			    /* Safe move */
			    if (rc > 0) goto nextstep;
			}
		    }
		}
	    }
	    if (nstock > 0 && mayDeal(0))
	    {
		int score= rateMove(stacks+stock[0].id, 0, 0, 0);
		Move *dealMove= newMove(MTYPE_STD, stock[0].id, 0, 0, 0, score, 0);
		insertAltMove(&moves, dealMove, score);
	    }
	    /* Try adding a redeal to the list. This won't do anything if
	     * rateRedeal() refuses the option. */
	    if (!redealOnlyWhenStuck || moves == NULL)
		savemove(MTYPE_REDEAL,0, 0, 0, 0, &moves);
	}

	if (moves)
	{
	    if (verbose > 3)
	    {
		printf("Move Options:\n");
		for (Move *m= moves; m != NULL; m= m->alt)
		    printf("        %s\n",moveStr(m,0,1));
	    }
	    /* Do the first move in the list */
	    doMove(moves);
	    /* Old moves list is now on history, get ready for a new one */
	    moves= NULL;
	}
	else
	{
	    /* Got no moves - we are stuck */
	    saveBest(gather);
	    if (verbose == 4)
	    {
		printf("\nDead End:\n");
		printState(stdout, stacks);
		printf("\n");
	    }

	    /* If we have no history, we are doomed */
	    if (!hist)
	    {
		if (verbose > 0)
		    printf("Stuck! pass=%d moves=%d backtracks=%d\n",
			passcnt,movecnt,backtracks);
		if (verbose > 1)
		    printBest(stdout, 1);
		cleanUp(keepinit);
		return 0;
	    }

	    /* If we have history, we can backtrack */
	    backtracks++;
	    while (hist != NULL)
	    {
		Move *t= hist;
		undoMove(t);
		if (hist->alt == NULL)
		{
		    /* Backed up to a move with no alternatives.  Keep going */
		    hist= t->prev;
		    free(t);
		    /* Hit the end of history - we really are stuck */
		    if (hist == NULL)
		    {
			if (verbose > 0)
			    printf("Stuck. pass=%d moves=%d backtracks=%d\n",
				passcnt,movecnt,backtracks);
			if (verbose > 1)
			    printBest(stdout, 1);
			cleanUp(keepinit);
			return 0;
		    }
		}
		else
		{
		    /* Execute the first alternative move, stop backtracking */
		    Move *altmove= t->alt;
		    hist= t->prev;
		    free(t);
		    doMove(altmove);
		    break;
		}
	    }
	}

	nextstep:;

	if (verbose > 4) printState(stdout, stacks);
    }

    saveBest(gather);
    if (verbose > 0)
	printf("Victory! pass=%d moves=%d backtracks=%d\n",
	    passcnt,movecnt,backtracks);
    if (verbose > 1)
	printBest(stdout, 0);
    cleanUp(0);
    return 1;
}
